class Solution(object):
    def maxSumBST(self, root):
        self.max_val = 0
        max_range = 10 ** 5

        def dfs(node):
            if not node:
                return max_range, max_range, max_range
            else:
                left_min, left_max, left_sum = dfs(node.left)
                right_min, right_max, right_sum = dfs(node.right)
                if left_min == max_range:
                    if right_min == max_range:
                        if not node.left and not node.right:
                            self.max_val = max(self.max_val, node.val)
                            return node.val, node.val, node.val
                        else:
                            return max_range, max_range, max_range
                    else:
                        if not node.left:
                            if node.val < right_min:
                                now_min = node.val
                                now_max = right_max
                                now_sum = node.val + right_sum
                                self.max_val = max(self.max_val, now_sum)
                                return now_min, now_max, now_sum
                            else:
                                return max_range, max_range, max_range
                        else:
                            return max_range, max_range, max_range
                else:
                    if right_min == max_range:
                        if not node.right:
                            if node.val > left_max:
                                now_min = left_min
                                now_max = node.val
                                now_sum = node.val + left_sum
                                self.max_val = max(self.max_val, now_sum)
                                return now_min, now_max, now_sum
                            else:
                                return max_range, max_range, max_range
                        else:
                            return max_range, max_range, max_range
                    else:
                        if left_max < node.val < right_min:
                            now_min = left_min
                            now_max = right_max
                            now_sum = node.val + left_sum + right_sum
                            self.max_val = max(self.max_val, now_sum)
                            return now_min, now_max, now_sum
                        else:
                            return max_range, max_range, max_range

        dfs(root)
        return self.max_val